package leetcode.median;

import leetcode.base.TreeNode;

/**
 * ClassName: $236_LowestCommonAncestor
 * Description:
 * date: 2022-02-20 15:12
 *
 * @author liyifan
 */
public class $236_LowestCommonAncestor {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 分情况讨论， q p 是否在root的同侧或异侧
        if (root == null) {return root;}
        if (p.val == root.val || q.val == root.val) {return root;}

        if (find(root.left, p) && find(root.left, q)) {
            // p、q都在root的左子树
            return lowestCommonAncestor(root.left, p, q);
        }
        if (find(root.right, q) && find(root.right, p)) {
            // p、q都在root的右子树
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }

    public boolean find(TreeNode root, TreeNode target){
        if (root == null){return false;}
        if (root.val == target.val) {
            return true;
        }
        return find(root.left, target) || find(root.right, target);
    }
}
